/**
 * 
 */
package calculation.passed2;

/**
 * @author Michael
 *
 */
public class SquareRoot {

	/**
	Implement int sqrt(int x).

	Compute and return the square root of x.
	 */
	public int sqrtIntNT(int x) {
		if (x == 0)
			return 0;
		double guess = x / 2.0;
		while (!isGood(guess, x)) {
			guess = (guess + x / guess) / 2.0;
		}

		return (int) guess;
	}

	private boolean isGood(double n, int n2) {

		if (Math.abs(n * n - n2) / n2 < 0.00000000001)
			return true;
		return false;
	}

	public static int sqrtIntBS(int n) {
		assert (n >= 0);

		if (n == 0)
			return 0;

		int low = 1;
		int high = n;
		while (high - low > 1) {
			int mid = low + (high - low) / 2;
			int quotient = n / mid;
			if (mid > quotient) {
				high = mid;
			} else {
				low = mid;
			}
		}

		return low;
	}

	// Best solution for sqrt double binary search
	public static double sqrtDoubleßBS(double number) {
		final double EPS = 0.0000000001;
		if (number < 0)
			return Double.NaN;
		if (number - 0 < EPS)
			return 0;

		double sqrt = 0;
		double low = 0;
		double high = number < 1 ? 1 : number;
		while (low < high) {
			sqrt = low + (high - low) / 2.0;
			if (isGoodEnough(sqrt, number)) {
				break;
			}
			if (sqrt < number / sqrt) {
				low = sqrt;
			} else { // sqrt > number / sqrt
				high = sqrt;
			}
		}

		return sqrt;
	}

	public static double sqrtBinarySearch(double number) {
		assert (number >= 0);

		final double EPS = 0.0000000000000000000001;
		double result = 0;
		double low = 0;
		double high = number > 1 ? number : 1;
		int loop = 1000;
		while (low < high && loop > 0) {
			result = low + (high - low) / 2.0;
			double sqr = result * result;
			if (Math.abs(sqr - number) < EPS) {
				break;
			} else if (sqr < number) {
				low = result;
			} else { // sqr > numaber
				high = result;
			}
		}

		return result;
	}

	/**
	Reference:
	http://hi.baidu.com/huangisland/blog/item/1e269d271eae5c6a35a80fe0.html

	f'(xn) = delta(y)/delta(x) = (f(xn) - 0) / (xn - xn+1)
	xn+1 = xn - f(xn)/f'(xn)

	f(x) = x^2 - n
	f'(x) = 2x

	xn+1 = (xn + n/xn) / 2
	*/
	public static double sqrtNewton(double number) {
		if (number < 0)
			return Double.NaN;
		if (number - 0 < 0.000000000000000000001)
			return 0;

		double result = number / 2.0;
		while (!isGoodEnough(result, number)) {
			result = (result + number / result) / 2.0;
		}

		return result;
	}

	private static boolean isGoodEnough(double guess, double sqr) {
		final double EPS = 0.00000000001;
		//return (Math.abs(guest * guess - sqr)) / sqr < EPS;
		return Math.abs(guess / sqr * guess - 1) < EPS;
	}

	private static boolean isCloseEnough(double guess, double number) {
		final double EPS = 0.00001;
		return (Math.abs(guess - number) / number) / number < EPS;
	}

	public static double cubtBinarySearch(double number) {
		if (number < 0)
			return -cubtBinarySearch(number);

		final double EPS = 0.00000001;
		double result = number;
		double low = 0;
		double high = number > 1 ? number : 1;
		int loop = 1000; // to avoid infinite loop
		while (low < high && loop-- > 0) { // low < high could be removed
			result = low + (high - low) / 2; // (low + high) / 2 could be overflow
			double product = result * result * result;
			if (Math.abs(product - number) < EPS) {
				break;
			} else if (product < number) {
				low = result;
			} else { // product > number
				high = result;
			}
		}

		return result;
	}

	/**
	 * 
	 */
	public SquareRoot() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		double[] tests = { 0.0, 1.0, 1.2, 0.2, 0.25, 0.36, 0.37, 15, 16, 25,
				25.5553232341, 100, 101 };
		//		for (int i = 0; i < tests.length; i++)
		//			System.out.println("cubtBinarySearch(" + tests[i] + "): " + cubtBinarySearch(tests[i]));
		//	
		//		int[] testsInt = { 0, 1, 2, 3, 4, 5, 8, 9, 10, 15, 16, 17 };
		//		for (int i = 0; i < testsInt.length; i++)
		//			System.out.println("sqrtIntBS(" + testsInt[i] + "): " + sqrtIntBS(testsInt[i]));

		double[] testsDouble = { 0, 4, 1.0e5, 2, 0.001, 0.1e-6, 1.0e20, 1.0e60 };
		for (int i = 0; i < testsDouble.length; i++)
			System.out.printf("sqrtNewton(%e): %e\n", testsDouble[i],
					sqrtDoubleßBS(testsDouble[i]));
	}

}
